Exemple de codage RSA - Corrigé

 Énoncé

1. Sachant que \(c=3\) , \(p=3\) et \(q=11\) , calculer \(N\) et \(n\) .

2. L'expéditeur doit convertir chaque lettre de son message (de rang \(a\) dans l'alphabet) en un nombre \(b\) tel que \(a^c \equiv b \ [N]\) . Compléter le tableau suivant pour trouver le nombre \(b\) correspondant aux lettres \(\text {A, B, C, D}\) et \(\text E\) :

\(\begin{align*}\renewcommand{\arraystretch}{1.2}\begin{array}{|c|c|c|c|}\hline \text{Lettre}& \text{Rang } a& a^c& b \equiv a^c \equiv ... \ [N]\\ \hline \text{A} &&&\\ \hline \text{B} &2&2^3=8&\\ \hline \text{C} &&&\\ \hline \text{D} &&&\\ \hline \text{E} &&&\\ \hline\end{array}\end{align*}\)  

3. Déterminer la valeur de \(d\) tel que \(1 \leqslant d et \(cd \equiv 1 \ [n]\) .

4. Pour décoder un nombre \(b\) , le destinataire calcule \(b'\) tel que \(b^d \equiv b' \ [N]\) , puis associe au nombre \(b\) la lettre de rang \(b'\) dans l'alphabet. Compléter le tableau suivant pour trouver les lettres correspondants aux nombres \(b\) donnés :

\(\begin{align*}\renewcommand{\arraystretch}{1.2}\begin{array}{|c|c|c|c|}\hline \text{Nombre } b& b^d& b' \equiv b^d \equiv ... \ [N]& \text{Lettre}\\ \hline 1&&&\\ \hline 8&8^7=2 \,097 \,152&&\\ \hline 14&&&\\ \hline 26&&&\\ \hline 27&&&\\ \hline 31&&&\\ \hline\end{array}\end{align*}\)   

Solution

1. On a \(N=pq=3 \times 11=33\) et \(n=(p-1)(q-1)=2 \times 10=20\) .

2.
\(\begin{align*}\renewcommand{\arraystretch}{1.2}\begin{array}{|c|c|c|c|}\hline \text{Lettre}& \text{Rang } a& a^c& b \equiv a^c \equiv ... \ [N]\\ \hline \text{A} &1&1^3=1&1\\ \hline \text{B} &2&2^3=8&8\\ \hline \text{C} &3&3^3=27&27\\ \hline \text{D} &4&4^3=64&31\\ \hline \text{E} &5&5^3=125&26\\ \hline\end{array}\end{align*}\)   

3. On cherche \(d\) tel que \(1 \leqslant d<20\) et \(3d \equiv 1 \ [20]\) . Comme \(3 \times 7=21 \equiv 1 \ [20]\) , on constate que \(d=7\) convient.

4. 
\(\begin{align*}\renewcommand{\arraystretch}{1.2}\begin{array}{|c|c|c|c|}\hline \text{Nombre } b& b^d& b' \equiv b^d \equiv ... \ [N]& \text{Lettre}\\ \hline 1&1^7=1&1&\text{A}\\ \hline 8&8^7=2 \,097 \,152&2&\text{B}\\ \hline 14&14^7=105 \,413 \,504&20&\text{T}\\ \hline 26&26^7=8 \,031 \,810 \,176&5&\text{E}\\ \hline 27&27^7=10 \,460 \,353 \,203&3&\text{C}\\ \hline 31&31^7=27 \,512\,614\,111&4&\text{D}\\ \hline\end{array}\end{align*}\)